package levelorder;

import entity.TreeNode;

import java.util.*;

public class RightSideView {
    /*
    * 199. 二叉树的右视图
    * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，
    * 按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    *
    * 二叉树的节点个数的范围是 [0,100]
    * -100 <= Node.val <= 100
    * */
    public static void main(String[] args){

    }

    // 我的想法：广度优先先层次遍历，然后取每层结果最右边的值
    // 过是能过，但你不觉得很蠢嘛！！！你就不会遍历的时候直接把最后一个元素放进去嘛？？？
    public List<Integer> mySolution(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                root = deque.pop();
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
                len--;
                if(len == 0)
                    res.add(root.val);
            }
        }
        return res;
    }

    // 深度优先
    // 时间和内存开销好像不如广度优先
    public List<Integer> solution(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        // 用与记录已经找过的深度和该深度下最右边的值
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int max_deep = -1;  // 维护已到达的最深深度
        LinkedList<TreeNode> nodeStack = new LinkedList<TreeNode>();// 节点栈
        LinkedList<Integer> depthStack = new LinkedList<Integer>();// 深度栈
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()){
            root = nodeStack.pop();
            int deep = depthStack.pop();
            if(root != null) {
                max_deep = Math.max(max_deep, deep);
                // 如果不存在对应深度的节点我们才插入
                if (!hashMap.containsKey(deep)) {
                    hashMap.put(deep, root.val);
                }

                nodeStack.push(root.left);
                nodeStack.push(root.right);
                depthStack.push(deep + 1);
                depthStack.push(deep + 1);
            }
        }

        for (int i = 0; i <= max_deep; i++) {
            res.add(hashMap.get(i));
        }
        return res;
    }
}
